//
// Created by ASUS on 2024/10/21/星期一.
//
#include <bits/stdc++.h>
using namespace std;

vector<int> manacher(string s) {
	string t="^#";
	for(auto c:s){
		t+=c;
		t+='#';
	}
	t+="$";
	int n=t.size();
	vector<int> r(n);
	for(int i=0,j=0;i<n;i++){
		if(2*j-i>=0&&j+r[j]>i){
			r[i]=min(r[2*j-i],j+r[j]-i);
		}
		while(i-r[i]>=0&&i+r[i]<n&&t[i-r[i]]==t[i+r[i]]){
			r[i]+=1;
		}
		if(i+r[i]>j+r[j]){
			j=i;
		}
	}
	return r;
}

bool isPalindrome(vector<int>&r,int left,int right){
	int middle = left + right + 2;
	return 2*r[middle] - 1 >= 2*(right - left);
}